#include "BinaryTree.h"

BinaryTreeNode * CreateBinaryTreeNode(int value)
{
    BinaryTreeNode * pNode = new BinaryTreeNode();
    pNode->m_nValue = value;
    pNode->m_pLeft = NULL;
    pNode->m_pRight = NULL;
    
    return pNode;
}

void ConnectTreeNodes(BinaryTreeNode * pParent, BinaryTreeNode * pLeft, BinaryTreeNode * pRight)
{
    if (pParent != NULL)
    {
        pParent->m_pLeft = pLeft;
        pParent->m_pRight = pRight;
    }
}

void PrintTreeNode(BinaryTreeNode * pNode)
{
    if (pNode != NULL)
    {
        cout << "value of this node is " << pNode->m_nValue << endl;

        if (pNode->m_pLeft != NULL)
            cout << "value of its left child is " << pNode->m_pLeft->m_nValue << endl;
        else
            cout << "left child is null." << endl;

        if (pNode->m_pRight != NULL)
            cout << "value of its right child is " << pNode->m_pRight->m_nValue << endl;
        else
            cout << "right child is null." << endl;
    }
    else
        cout << "this node is null. " << endl;
}

void PrintTree(BinaryTreeNode * pRoot)
{
    PrintTreeNode(pRoot);

    if (pRoot != NULL)
    {
        if(pRoot->m_pLeft != NULL)
            PrintTree(pRoot->m_pLeft);
        
        if(pRoot->m_pRight != NULL)
            PrintTree(pRoot->m_pRight);
    }
}

void DestroyTree(BinaryTreeNode * pRoot)
{
    if (pRoot != NULL)
    {
        BinaryTreeNode * pLeft = pRoot->m_pLeft;
        BinaryTreeNode * pRight = pRoot->m_pRight;

        delete pRoot;
        pRoot = NULL;

        DestroyTree(pLeft);
        DestroyTree(pRight);
    }
}

BinaryTreeNode* ConstructCore(int* startPreorder, int* endPreorder, int* startInorder, int* endInorder);
BinaryTreeNode* Construct(int* preorder, int* inorder, int length)
{
    if(preorder == NULL || inorder == NULL || length <= 0)
        return NULL;

    return ConstructCore(preorder, preorder + length - 1,
                    inorder, inorder + length - 1);
}
// 依据前序遍历和中序遍历构建二叉树
BinaryTreeNode* ConstructCore(int* startPreorder, int* endPreorder, int* startInorder, int* endInorder)
{
    // 前序遍历的第一个值为根结点值
    int rootValue = startPreorder[0];
    BinaryTreeNode* root = new BinaryTreeNode();
    root->m_nValue = rootValue;
    root->m_pLeft = root->m_pRight = NULL;
    
    if(startPreorder == endPreorder)
    {
        if(startInorder == endInorder && *startPreorder == *startInorder)
            return root;
        else
        {
            cout << "invalid input." << endl;
            exit(0);
        }
    }
    // 在中序遍历中找到根节点的值
    int* rootInorder = startInorder;
    while(rootInorder <= endInorder && *rootInorder != rootValue)
        ++rootInorder;

    if(rootInorder == endInorder && *rootInorder != rootValue)
    {    
        cout << "invalid input" << endl;
        exit(0);
    }   
    
    int leftLength = rootInorder - startInorder;
    int* leftPreorderEnd = startPreorder + leftLength;
    // 构建左子树
    if(leftLength > 0)
    {
        root->m_pLeft = ConstructCore(startPreorder + 1, leftPreorderEnd, 
                                startInorder, rootInorder - 1);
    }
    // 构建右子树
    if(leftLength < endPreorder - startPreorder)
    {
        root->m_pRight = ConstructCore(leftPreorderEnd + 1, endPreorder,
                                rootInorder + 1, endInorder);
    }

    return root;
}


bool DoesTree1HaveTree2(BinaryTreeNode * pTree1, BinaryTreeNode * pTree2)
{
    if(pTree2 == NULL)
        return true;
    if(pTree1 == NULL)
        return false;
    if(pTree1->m_nValue != pTree2->m_nValue)
        return false;

    return DoesTree1HaveTree2(pTree1->m_pLeft, pTree2->m_pLeft) && DoesTree1HaveTree2(pTree1->m_pRight, pTree2->m_pRight);
}

bool HasSubTree(BinaryTreeNode * pRoot1, BinaryTreeNode * pRoot2)
{
    bool result = false;

    if(pRoot1 != NULL && pRoot2 != NULL)
    {
        if (pRoot1->m_nValue == pRoot2->m_nValue)
            result = DoesTree1HaveTree2(pRoot1, pRoot2);
        if(!result)
            result = HasSubTree(pRoot1->m_pLeft, pRoot2);
        if(!result)
            result = HasSubTree(pRoot1->m_pRight, pRoot2);
    }
    return result;
}

void MirrorBinaryTree_Recursively(BinaryTreeNode * pBinaryTreeRoot)
{
    if (pBinaryTreeRoot == NULL || (pBinaryTreeRoot->m_pLeft == NULL && pBinaryTreeRoot->m_pRight))
        return;

    BinaryTreeNode * pTemp = pBinaryTreeRoot->m_pLeft;
    pBinaryTreeRoot->m_pLeft = pBinaryTreeRoot->m_pRight;
    pBinaryTreeRoot->m_pRight = pTemp;

    if(pBinaryTreeRoot->m_pLeft)
        MirrorBinaryTree_Recursively(pBinaryTreeRoot->m_pLeft);

    if(pBinaryTreeRoot->m_pRight)
        MirrorBinaryTree_Recursively(pBinaryTreeRoot->m_pRight);
}
